package demo2;
import java.util.*;
public class Solution {
    //1.剑指 Offer 63. 股票的最大利润(贪心)
    public int maxProfit(int[] prices) {
        //贪心
        int len = prices.length;
        if(len == 0) {
            return 0;
        }
        int max = 0;
        int now = prices[0];//当前买入股票需要的钱
        for(int i = 1; i < len; i++) {
            if(prices[i] - now > max) {
                max = prices[i] - now;
            }
            if(now > prices[i]) {
                now = prices[i];
            }
        }
        return max;
    }

    //剑指 Offer 63. 股票的最大利润(动态规划)
//    public int maxProfit(int[] prices) {
//        int len = prices.length;
//        if(len < 2) return 0;//不可能卖出
//        int[] dp = new int[len];
//        int cost = prices[0];//初始化成本
//        for(int i = 1; i < len; i++) {
//            dp[i] = Math.max(dp[i - 1], prices[i] - cost);
//            cost = Math.min(cost, prices[i]);
//        }
//        return dp[len - 1];
//    }

    //2. 岛屿数量(dfs)
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {//是岛屿，就把这个岛屿清除，并计数
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        if(i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
    //岛屿数量(bfs)
//    public int numIslands(char[][] grid) {
//        int count = 0;
//        for(int i = 0; i < grid.length; i++) {
//            for(int j = 0; j < grid[0].length; j++) {
//                if(grid[i][j] == '1') {//是岛屿，就把这个岛屿清除，并计数
//                    bfs(grid, i, j);
//                    count++;
//                }
//            }
//        }
//        return count;
//    }
    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            i = cur[0];
            j = cur[1];
            if(i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                queue.offer(new int[] {i + 1, j});
                queue.offer(new int[] {i - 1, j});
                queue.offer(new int[] {i, j - 1});
                queue.offer(new int[] {i, j + 1});
            }
        }
    }
    //3.括号生成(dfs)
//    public List<String> generateParenthesis(int n) {
//        List<String> ret = new ArrayList<>();
//        if(n == 0) {
//            return null;
//        }
//        dfs(n, "", ret, 0, 0);
//        return ret;
//    }
//    private void dfs(int n, String path, List<String> ret, int left, int right) {
//        if(left > n || right > left) {//左括号大于n肯定错误；右括号不可以比左括号多
//            return;
//        }
//        if(path.length() == n * 2) {//一个括号两个字符
//            ret.add(path);
//            return;
//        }
//        dfs(n, path + "(", ret, left + 1, right);
//        dfs(n, path + ")", ret, left, right + 1);
//    }
//    //4.汉明距离(位运算)
//    public int hammingDistance(int x, int y) {
//        int count = 0;
//        for(int i = 0; i < 32; i++) {
//            if((x & 1) != (y & 1)) {
//                count++;
//            }
//            x >>= 1;
//            y >>= 1;
//        }
//        return count;
//    }
//    //5.全排列(回溯剪枝)
//    List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> permute(int[] nums) {
//        List<Integer> path = new ArrayList<>();
//        dfs(nums, path);
//        return ret;
//    }
//    private void dfs(int[] nums, List<Integer> path) {
//        if(path.size() == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(path.contains(nums[i])) {//剪枝
//                continue;
//            }
//            path.add(nums[i]);
//            dfs(nums, path);
//            path.remove(path.size() - 1);
//        }
//    }
//    //6.电话号码的字母组合(回溯去重)
//    String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//    List<String> ret = new ArrayList<>();
//    public List<String> letterCombinations(String digits) {
//        if(digits.length() == 0) {
//            return ret;
//        }
//        dfs(new StringBuilder(), digits, 0);
//        return ret;
//    }
//    private void dfs(StringBuilder path, String digits, int index) {
//        if(index == digits.length()) {
//            ret.add(path.toString());
//            return;
//        }
//        int num = digits.charAt(index) - '0';
//        String mapGet = map[num];
//        for(int i = 0; i < mapGet.length(); i++) {
//            path.append(mapGet.charAt(i));
//            dfs(path, digits, index + 1);
//            //剪枝
//            path.deleteCharAt(path.length() - 1);
//        }
//    }
//    //7.找出数组的最大公约数
//    public int findGCD(int[] nums) {
//        if(nums.length <= 1) {
//            return nums[0];
//        }
//        int max = nums[0];
//        int min = nums[0];
//        //找出最大值和最小值
//        for(int i = 0; i < nums.length; i++) {
//            if(nums[i] > max) {
//                max = nums[i];
//            }
//            if(nums[i] < min) {
//                min = nums[i];
//            }
//        }
//        //求最大公约数
//        for(int i = min; i > 0; i--) {
//            if(min % i == 0 && max % i == 0) {
//                return i;
//            }
//        }
//        return 1;
//    }
//    //8.全排列(二刷)
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> permute(int[] nums) {
//        List<Integer> path = new ArrayList<>();
//        dfs(nums, path);
//        return ret;
//    }
//    private void dfs(int[] nums, List<Integer> path) {
//        if(path.size() == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(path.contains(nums[i])) {
//                continue;
//            }
//            path.add(nums[i]);
//            dfs(nums, path);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    //9. 组合总和(回溯)
//    private List<List<Integer>> ret = new ArrayList<>();
//    private int target;
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        this.target = target;
//        List<Integer> path = new ArrayList<>();
//        dfs(candidates, path, 0);
//        return ret;
//    }
//    private void dfs(int[] candidates, List<Integer> path, int sum) {
//        if(sum == target) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }else if(sum > target) {
//            return;
//        }
//        for(int i = 0; i < candidates.length; i++) {
//            if(!path.isEmpty() && path.get(path.size() - 1) > candidates[i]) {
//                continue;
//            }
//            path.add(candidates[i]);
//            dfs(candidates, path, sum + candidates[i]);
//            //剪枝
//            path.remove(path.size() - 1);
//
//        }
//    }
//    //10.最长递增子序列(动态规划)
//    public int lengthOfLIS(int[] nums) {
//        //动态:max(dp[i], dp[j] + 1)
//        int ret = 1;
//        int len = nums.length;
//        int[] dp = new int[len];
//        dp[0] = 1;
//        for(int i = 1; i < len; i++) {
//            dp[i] = 1;//初始化
//            for(int j = 0; j < i; j++) {
//                if(nums[i] > nums[j]) {
//                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//                }
//            }
//            ret = Math.max(ret, dp[i]);
//        }
//        return ret;
//    }
}
